package com.ly.algorithm.leetcode.tree;

import java.util.HashMap;
import java.util.Map;

/**
 * @Classname Problem106
 * @Description
 * 你可以假设树中没有重复的元素。
 *
 * 例如，给出
 *
 * 中序遍历 inorder = [9,3,15,20,7]
 * 后序遍历 postorder = [9,15,7,20,3]
 * 返回如下的二叉树：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 * @Date 2020/9/25 21:32
 * @Author 冷心影翼
 */
public class Problem106 {

    public static void main(String[] args) {
        Solution106 solution106 = new Solution106();
        TreeNode treeNode = solution106.buildTree(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3});
        System.out.println(treeNode.right.left);
    }

}

class Solution106 {
    public Map<Integer, Integer> map = new HashMap<>();
    public int pos;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int i = 0;
        for (int item : inorder) {
            map.put(item,i++);
        }
        pos = postorder.length-1;
        return buildTree(postorder,0,postorder.length-1);
    }

    public TreeNode buildTree(int[] postorder,int left,int right) {
        if(left>right) {
            return null;
        }
        int rootVal = postorder[pos];
        Integer index = map.get(rootVal);
        TreeNode root = new TreeNode(rootVal);
        pos--;
        root.right = buildTree(postorder,index+1,right);
        root.left = buildTree(postorder,left,index-1);

        return root;
    }
}